package 我的Java学习_算法基础.day_08;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2021/8/26 - 08 - 26 - 13:30
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _137_最长递增子序列 {
    public static void main(String[] args) {
        int[] arr = {4, 2, 3, 1, 2, 6};
        System.out.println(f(arr));
        System.out.println(dp(arr));
        System.out.println(dp1(arr));
    }

    //暴力解法
    private static int f(int[] arr) {
        int maxCount = 0;
        List<Integer> maxList = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            List<Integer> list = new ArrayList<>();
            int p = i;
            list.add(arr[i]);
            int count = 1;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[p]) {
                    list.add(arr[j]);
                    count++;
                    p=j;//标记这个数，下一次找比这个大的
                }
            }
            if (count > maxCount) {
                maxList = list;
                maxCount = count;
            }
        }
        for (Integer e:maxList
             ) {
            System.out.print(e+" ");
        }
        System.out.println();
        return maxCount;
    }

    //动规
    static int[] dp;

    //dp[i]以arr[i]结尾的最长子序列
    private static int dp(int[] arr) {
        dp = new int[arr.length];
        dp[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            int count = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) {//最长加1
                    count = Math.max(count, dp[j] + 1);
                }
            }
            dp[i] = count;
        }
        int answer = -1;
        for (int i = 0; i < dp.length; i++) {//取dp数组中最大的那个
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }

    //动规优化
    //优化后可以达到O(NlgN)
    private static int dp1(int[] arr) {
        dp = new int[arr.length + 1];
        dp[1] = arr[0];//长度为1的最长递增子序列，初始化为第一个元素
        int p = 1;//记录dp更新的最后位置
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > dp[p]) {//更新长度和p指针
                dp[p + 1] = arr[i];
                p++;
            } else {
                //扫描dp数组，替换第一个arr[i]比大的dp
//                for (int j = 0; j<= p ; j++) {
//                    if(dp[j]>arr[i]){
//                        dp[j] = arr[i];
//                    }
//                }
                //优化
                int indexOfFirstBigger = indexOfFirstBigger(dp, arr[i], 1, p);//dp数组下标从1开始0不用
                if (indexOfFirstBigger != -1)
                    dp[indexOfFirstBigger] = arr[i];
            }
        }
        return p;
    }
    //dp数组是从小到大的
    public static int indexOfFirstBigger(int[] dp, int v, int l, int r) {
        while (l <= r) {
            int mid =(l + r) >> 1;
            if (dp[mid] > v) {
                r = mid; //保留大于v的下标以防是第一个
            } else {
                l = mid + 1;
            }
            if (l == r && dp[l] > v) {
                return l;
            }
        }
        return -1;
    }

}
